red green trees
https://twitter.com/zakuro9715/status/1708646757465538961 Roslyn で発明された red green trees、lossless syntax trees と呼ばれたりもしていて、rust-analyzer とか swift とか biome(rome) とか最近の言語処理系で結構使われているっぽいが、その割には解説が少ない
不完全なコードを表現できるとか、木の一部分を差し替えられるとかのメリットがあるので、ソースコードの変更があったときに変更部分だけパースして差し替えたりできる。
https://twitter.com/kinaba/status/1708816703625556245 具象構文木にソースコード上の位置情報とか含めるんじゃなくて、functionalな純粋な構文の木構造と、位置情報を付加したzipper、という二段構えがいいよということか。なるほど確かにそれはすごくそんな気がする。今度言語処理系書くときやってみよう。
https://twitter.com/zakuro9715/status/1708755898817265932
Red Green Trees は結構面白くて、外部に露出する木のノード(RedNode)が内部ノード(GreenNode)を持っていて、Red は親の Red を持ち、Green は子の Green とトークンとかを持つ。Red はボトムアップに辿れて Green はトップダウンに走査できる。 最初はだからどうしたと思ったけど、たしかに便利
Red Green なのは使っていたマーカーの色で意味はないらしい。分かりづらいので、実装ではred green の名前ではなくなっていたりするが、 rust-analyzer のライブラリである rowan では何故か green だけが残っているので、経緯を知らないと名前の意味がわからない
rust-analyzer/docs/dev/syntax.md at master · rust-lang/rust-analyzer
#構文木